/*
 * xtc - The eXTensible Compiler
 * Copyright (C) 2007-2008 Robert Grimm
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * version 2 as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
 * USA.
 */
package xtc.parser;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import xtc.Constants;

import xtc.tree.Attribute;
import xtc.tree.Visitor;

import xtc.type.AST;
import xtc.type.Type;

import xtc.util.Runtime;

/**
 * Visitor to inject source code annotations into a grammar.
 *
 * <p />This visitor distinguishes between bindable elements, i.e.,
 * elements that would contribute to the value of a generic
 * production, and valuable element, i.e., elements that can be
 * rewritten to have a semantic value.  The latter include voided
 * elements and references to void productions that consume the input.
 *
 * <p />For directly left-recursive alternatives in generic
 * productions, this visitor may annotate the last sequence with the
 * {@link Properties#FORMATTING} property, indicating valuable
 * elements that need to be captured in the promise generated by
 * {@link DirectLeftRecurser}.
 *
 * <p />This visitor assumes that the entire grammar is contained in a
 * single module, that the grammar has been tokenized, and that
 * productions that may consume the input have been marked.
 *
 * @see Tokenizer
 * @see Analyzer#consumesInput(Element)
 *
 * @author Robert Grimm
 * @version $Revision: 1.33 $
 */
public class Annotator extends Visitor {

  /** The marker for synthetic variables. */
  public static final String MARKER = "pt";

  // ==========================================================================

  /** A mutable boxed integer. */
  public static class Index {

    /** The actual index. */
    public int index;

    /** Create a new index initialized to -1. */
    public Index() {
      index = -1;
    }

    /**
     * Create a copy of the specified index.
     *
     * @param index The index.
     */
    public Index(Index index) {
      this.index = index.index;
    }

  }

  // ==========================================================================

  /** A pair of indices. */
  public static class IndexPair {

    /** The first index. */
    public int index1;

    /** The second index. */
    public int index2;

    /** Create a new pair of indices, initialized to -1. */
    public IndexPair() {
      index1 = -1;
      index2 = -1;
    }

  }

  // ==========================================================================

  /**
   * A visitor to detect whether productions need to be rewritten.
   * This visitor detects non-left-recursive generic or list-valued
   * productions that contain:<ol>
   *
   * <li>a bindable element with a list value preceded by one or more
   * valuable elements, but no bindable elements;</li>
   *
   * <li>a bindable element with a list value followed by one or more
   * valuable elements, but no more bindable elements.</li>
   *
   * </ol>
   *
   * For each such production, this visitor sets the {@link
   * Properties#SPLIT} property.  For each (flattened) alternative
   * that contains any of the two cases, it also annotates the last
   * sequence with a {@link Annotator.IndexPair}.  The first index is
   * non-negative for the first case.  The second index is
   * non-negative for the second case.
   */
  public class Detector extends Visitor {

    /** The flag for whether the production needs to be split. */
    protected boolean needToSplit;

    /** The list of elements. */
    protected List<Element> elements;
  
    /** Create a new detector. */
    public Detector() {
      elements = new ArrayList<Element>();
    }

    /** Visit the specified module. */
    public void visit(Module m) {
      // Initialize the per-grammar state.
      analyzer.register(this);
      analyzer.init(m);

      // Process the productions.
      for (Production p : m.productions) {
        // Only truly generic and list-vallued productions are
        // candidates, since they determine a program's AST.  However,
        // we cannot split directly left-recursive productions because
        // all component values must be part of the resulting node,
        // whose creation is delayed through a promise.
        if (((! Generifier.isGeneric((FullProduction)p)) &&
             (! isList(p.type))) ||
            DirectLeftRecurser.isTransformable((FullProduction)p)) {
          continue;
        }

        // Do the work.
        needToSplit = false;
        analyzer.process(p);
        if (needToSplit) p.setProperty(Properties.SPLIT, Boolean.TRUE);
      }
    }

    /** Visit the specified production. */
    public void visit(FullProduction p) {
      dispatch(p.choice);
    }

    /** Visit the specified choice. */
    public void visit(OrderedChoice c) {
      for (Sequence alt : c.alternatives) dispatch(alt);
    }

    /** Visit the specified sequence. */
    public void visit(Sequence s) {
      // Remember the current number of elements.
      final int base = elements.size();

      // Add this sequence's elements to the list of elements.
      for (Iterator<Element> iter = s.elements.iterator(); iter.hasNext(); ) {
        Element e = iter.next();

        if ((! iter.hasNext()) && (e instanceof OrderedChoice)) {
          // Continue with the trailing choice.
          dispatch(e);
        } else {
          // Add the current element to the list of traversed elements.
          elements.add(e);
        }
      }

      // Actually process the elements.
      if (! s.hasTrailingChoice()) {
        // Flag for at least one bindable element.
        boolean hasBindable    = false;
        // Flag for at least one valuable element.
        boolean hasValuable    = false;
        // Index of the first bindable element with a list value.
        int     first          = -1;
        // Index of the last bindable element with a list value.
        int     last           = -1;
        // Flag for a bindable element with a list value succeeded by
        // one or more valuable elements.
        boolean hasFollowing   = false;

        final int size = elements.size();
        for (int i=0; i<size; i++) {
          final Element e = elements.get(i);

          if (analyzer.isBindable(e)) {
            if (AST.isList(analyzer.type(e))) {
              if ((! hasBindable) && hasValuable) first = i;
              last = i;
            } else {
              last = -1;
            }

            hasFollowing = false;
            hasBindable  = true;

          } else if (isValuable(e)) {
            if (-1 != last) hasFollowing = true;

            hasValuable = true;
          }
        }
        
        if (-1 != first || hasFollowing) {
          IndexPair result = new IndexPair();
          if (-1 != first)  result.index1 = first;
          if (hasFollowing) result.index2 = last;
          needToSplit = true;
          s.setProperty(Properties.SPLIT, result);
        }
      }

      // Remove any elements added by this method invocation.
      if (0 == base) {
        elements.clear();
      } else {
        elements.subList(base, elements.size()).clear();
      }      
    }

  }

  // ==========================================================================

  /**
   * A visitor to rewrite productions.  This visitor rewrites
   * productions that have been marked with the {@link
   * Properties#SPLIT} property to generate the same basic AST with
   * annotations as without annotations.
   *
   * @see Annotator.Detector
   */
  public class Rewriter extends Visitor {

    /** The list of elements. */
    protected List<Element> elements;

    /** The flag for whether the current choice is top-level. */
    protected boolean isTopLevel;

    /** The current top-level alternative. */
    protected Sequence alternative;

    /** The list of replacement sequences. */
    protected List<Sequence> replacements;

    /** Create a new rewriter. */
    public Rewriter() {
      elements = new ArrayList<Element>();
    }

    /** Visit the specified module. */
    public void visit(Module m) {
      // Initialize the per-grammar state.
      analyzer.register(this);
      analyzer.init(m);

      for (int i=0; i<m.productions.size(); i++) {
        FullProduction p = (FullProduction)m.productions.get(i);

        // We only rewrite marked productions.
        if (! p.getBooleanProperty(Properties.SPLIT)) continue;

        // Process the production.
        analyzer.startAdding();
        analyzer.process(p);

        // If there are new productions, add them to the grammar and
        // make sure they are not processed.
        i += analyzer.addNewProductionsAt(i+1);
      }
    }

    /** Visit the specified production. */
    public void visit(FullProduction p) {
      isTopLevel = true;
      dispatch(p.choice);
    }

    /** Visit the specified choice. */
    public void visit(OrderedChoice c) {
      // Track whether this choice is top-level.
      boolean top = isTopLevel;
      isTopLevel  = false;

      // Make space for the replacements.
      if (top) replacements = new ArrayList<Sequence>(c.alternatives.size());

      // Process the alternatives.
      for (Sequence s : c.alternatives) {
        if (top) alternative = s;
        dispatch(s);
      }

      // Patch the top-level choice's alternatives.
      if (top) c.alternatives = replacements;
    }

    /** Visit the specified sequence. */
    public void visit(Sequence s) {
      // Remember the current number of elements.
      final int base = elements.size();

      // Add this sequence's elements to the list of elements.
      for (Iterator<Element> iter = s.elements.iterator(); iter.hasNext(); ) {
        Element e = iter.next();

        if ((! iter.hasNext()) && (e instanceof OrderedChoice)) {
          // Continue with the trailing choice.
          dispatch(e);
        } else {
          // Add the current element to the list of traversed elements.
          elements.add(e);
        }
      }

      // Actually process the elements.
      if (! s.hasTrailingChoice()) {
        IndexPair split = (IndexPair)s.getProperty(Properties.SPLIT);

        if (null == split) {
          // There's nothing to split here.  Just construct the
          // replacement sequence.
          Sequence r = new Sequence(new ArrayList<Element>(elements));
          r.name     = alternative.name;
          r.setLocation(alternative);
          replacements.add(r);

        } else {
          // There's something to split here.
          Production p = analyzer.current();

          // Determine the node marker for the new production.  If the
          // elements have a node marker, use the last one; otherwise,
          // use one for the current production.
          NodeMarker mark = null;
          for (Element e : elements) {
            if (e instanceof NodeMarker) mark = (NodeMarker)e;
          }
          if (null == mark) mark = new NodeMarker(p.name.name);

          // Determine the nonterminal and only alternative for the
          // new production.
          final NonTerminal nt = analyzer.split();
          final Sequence    alt;
          if (-1 == split.index2) {
            alt = new Sequence(elements.size() - split.index1 + 1);
            alt.addAll(elements.subList(split.index1, elements.size()));
            alt.add(mark);

          } else if (-1 == split.index1) {
            alt = new Sequence(split.index2 + 2);
            alt.addAll(elements.subList(0, split.index2 + 1));
            alt.add(mark);

          } else {
            alt = new Sequence(split.index2 - split.index1 + 2);
            alt.addAll(elements.subList(split.index1, split.index2 + 1));
            alt.add(mark);
          }
          alt.name = alternative.name;
          alt.setLocation(alternative);

          // Create the new production.
          FullProduction q =
            new FullProduction(new ArrayList<Attribute>(p.attributes),
                               AST.GENERIC, nt,
                               nt.qualify(analyzer.module().name.name),
                               new OrderedChoice(alt));
          // Do not inherit any public, explicit, stateful, or
          // restting attribute.
          q.attributes.remove(Constants.ATT_PUBLIC);
          q.attributes.remove(Constants.ATT_EXPLICIT);
          q.attributes.remove(Constants.ATT_STATEFUL);
          q.attributes.remove(Constants.ATT_RESETTING);
          // But do ensure that the new production is transient.
          if (! q.hasAttribute(Constants.ATT_TRANSIENT) &&
              ! q.hasAttribute(Constants.ATT_INLINE)) {
            q.attributes.add(Constants.ATT_TRANSIENT);
          }

          // Document activity under verbose mode.
          if (runtime.test("optionVerbose")) {
            System.err.println("[Lifting split sequence into new production " +
                               q.qName + ']');
          }

          // Add the new production to the grammar.
          analyzer.add(q);

          // Create the replacement.
          final Sequence r;
          if (-1 == split.index2) {
            r = new Sequence(split.index1 + 1);
            r.addAll(elements.subList(0, split.index1));
            r.add(new Binding(CodeGenerator.VALUE, nt));

          } else if (-1 == split.index1) {
            r = new Sequence(elements.size() - split.index2);
            r.add(new Binding(CodeGenerator.VALUE, nt));
            r.addAll(elements.subList(split.index2 + 1, elements.size()));

          } else {
            r = new Sequence(split.index1 + elements.size() - split.index2);
            r.addAll(elements.subList(0, split.index1));
            r.add(new Binding(CodeGenerator.VALUE, nt));
            r.addAll(elements.subList(split.index2 + 1, elements.size()));
          }
          r.name = alternative.name;
          r.setLocation(alternative);
          replacements.add(r);
        }
      }

      // Remove any elements added by this method.
      if (0 == base) {
        elements.clear();
      } else {
        elements.subList(base, elements.size()).clear();
      }
    }

  }

  // ==========================================================================

  /** The runtime. */
  protected final Runtime runtime;

  /** The analyzer. */
  protected final Analyzer analyzer;

  /** The flag for whether the current production is generic. */
  protected boolean isGeneric;

  /** The flag for whether the current production is list-valued. */
  protected boolean isList;

  /**
   * The flag for whether the current production or sequence is
   * directly left-recursive.
   */
  protected boolean isRecursive;

  /** The flag for whether the current choice is top-level. */
  protected boolean isTopLevel;

  /** 
   * The index of the next sequence to process.  The stacks capturing
   * the state for tracking bindable and valuable must have as many
   * elements as indicated by this index.
   */
  protected int toProcessIdx;

  /** The elements as a list of sequences. */
  protected List<Sequence> sequences;

  /**
   * The list of bindings for valuable elements before the regular,
   * bindable value, organized as a stack of copies.
   *
   * @see #toProcessIdx
   */
  protected List<List<Binding>> before;

  /**
   * The index of the sequence with the regular, bindable value,
   * organized as a stack of copies.  A value of -1 indicates no
   * bindable value.
   *
   * @see #toProcessIdx
   */
  protected List<Index> sequenceIdx;

  /**
   * The index of the regular, bindable value, organized as a stack of
   * copies.  A value of -1 indicates no bindable value.
   *
   * @see #toProcessIdx
   */
  protected List<Index> elementIdx;

  /**
   * The list of bindings for valuable elements after the regular,
   * bindable value, organized as a stack of copies.
   *
   * @see #toProcessIdx
   */
  protected List<List<Binding>> after;

  /**
   * Create a new annotator.
   *
   * @param runtime The runtime.
   * @param analyzer The analyzer utility.
   */
  public Annotator(Runtime runtime, Analyzer analyzer) {
    this.runtime      = runtime;
    this.analyzer     = analyzer;
    this.toProcessIdx = 0;
    this.sequences    = new ArrayList<Sequence>();
    this.before       = new ArrayList<List<Binding>>();
    this.sequenceIdx  = new ArrayList<Index>();
    this.elementIdx   = new ArrayList<Index>();
    this.after        = new ArrayList<List<Binding>>();
  }

  /**
   * Push a copy of the state for tracking bindable and valuable
   * elements.  This method pushes copies of the top elemens of the
   * tracking state onto the respective stacks.  If the stacks are
   * empty, it initializes the lists of bindings with empty lists and
   * the indices with -1.
   */
  protected void push() {
    assert before.size() == sequenceIdx.size();
    assert before.size() == elementIdx.size();
    assert before.size() == after.size();

    if (0 == before.size()) {
      before.add(new ArrayList<Binding>());
      sequenceIdx.add(new Index());
      elementIdx.add(new Index());
      after.add(new ArrayList<Binding>());
    } else {
      before.add(new ArrayList<Binding>(before.get(before.size()-1)));
      sequenceIdx.add(new Index(sequenceIdx.get(sequenceIdx.size()-1)));
      elementIdx.add(new Index(elementIdx.get(elementIdx.size()-1)));
      after.add(new ArrayList<Binding>(after.get(after.size()-1)));
    }
  }

  /**
   * Pop the top elements from the state for tracking bindable and
   * valuable elements.
   */
  protected void pop() {
    assert before.size() == sequenceIdx.size();
    assert before.size() == elementIdx.size();
    assert before.size() == after.size();

    before.remove(before.size()-1);
    sequenceIdx.remove(sequenceIdx.size()-1);
    elementIdx.remove(elementIdx.size()-1);
    after.remove(after.size()-1);
  }

  /**
   * Reset the current state for tracking bindable and valuable
   * elements.  This method replaces the current lists of bindings
   * with new, empty lists and sets the current indices to -1.
   */
  protected void reset() {
    before.set(before.size()-1, new ArrayList<Binding>());
    sequenceIndex().index = -1;
    elementIndex().index  = -1;
    after.set(after.size()-1, new ArrayList<Binding>());
  }

  /**
   * Get the current list of bindings before the regular value.
   *
   * @return The current list of bindings.
   */
  protected List<Binding> before() {
    return before.get(before.size()-1);
  }

  /**
   * Get the current sequence index of the regular value.
   *
   * @return The current sequence index.
   */
  protected Index sequenceIndex() {
    return sequenceIdx.get(sequenceIdx.size()-1);
  }

  /**
   * Get the current element index of the regular value.
   *
   * @return The current element index.
   */
  protected Index elementIndex() {
    return elementIdx.get(elementIdx.size()-1);
  }

  /**
   * Get the current list of bindings after the regular value.
   *
   * @return The current list of bindings.
   */
  protected List<Binding> after() {
    return after.get(after.size()-1);
  }

  /**
   * Determine whether the specified element is valuable.  This method
   * returns <code>true</code> if the specified element has a semantic
   * value or can be rewritten to yield a semantic value.  Rewriting
   * includes eliminating any voided element or converting a void
   * production into a production returning a semantic value.
   *
   * @param e The element.
   * @return <code>true</code> if the specified element is valuable.
   */
  protected boolean isValuable(Element e) {
    switch (e.tag()) {
    case VOIDED:
      assert isValuable(((VoidedElement)e).element);
      return true;
    case NONTERMINAL:
      return isValuable(analyzer.lookup((NonTerminal)e));
    case CHOICE:
    case OPTION:
    case REPETITION:
    case ANY_CHAR:
    case CHAR_CLASS:
    case CHAR_LITERAL:
    case STRING_LITERAL:
    case STRING_MATCH:
    case PARSE_TREE_NODE:
    case BINDING:
      return true;
    default:
      return false;
    }
  }

  /**
   * Determine whether the specified element is a possibly bound or
   * voided parse tree node.
   *
   * @param e The element.
   * @return <code>true</code> if the specified element is a parse
   *   tree node.
   */
  protected boolean isParseTreeNode(Element e) {
    switch (e.tag()) {
    case VOIDED:
    case BINDING:
      return isParseTreeNode(((UnaryOperator)e).element);
    case PARSE_TREE_NODE:
      return true;
    default:
      return false;
    }
  }

  /**
   * Determine whether a bindable element has been processed.
   *
   * @see Analyzer#isBindable(Element)
   *
   * @return <code>true</code> if a bindable element has been
   *   processed.
   */
  protected boolean hasBindable() {
    return -1 != sequenceIndex().index;
  }

  /**
   * Determine whether any valuable elements have been processed.
   *
   * @see #isValuable(Element)
   *
   * @return <code>true</code> if any valuable elements have been
   *   processed.
   */
  protected boolean hasValuable() {
    return (0 < before().size()) || (0 < after().size());
  }

  /**
   * Determine whether the specified element already is bound and
   * voided.
   *
   * @param e The element.
   * @return <code>true</code> if the specified element already is
   *   bound and voided.
   */
  protected boolean isBoundAndVoided(Element e) {
    return (e instanceof VoidedElement) &&
      (((VoidedElement)e).element instanceof Binding);
  }

  /**
   * Bind and void the specified element.  The specified element must
   * be valuable, i.e., can be rewritten to yield a semantic value.
   *
   * @see #isValuable(Element)
   *
   * @param e The element.
   * @return The voided, bound element.
   */
  protected VoidedElement bindAndVoid(final Element e) {
    Element tmp = e;

    // Strip any voided element.
    if (tmp instanceof VoidedElement) {
      tmp = ((VoidedElement)tmp).element;
    }

    // Make sure the element is bound.
    if (tmp instanceof Binding) {
      // Preserve already existing bindings, unless they refer to
      // yyValue.
      Binding b = (Binding)tmp;
      if (CodeGenerator.VALUE.equals(b.name)) {
        b.name = analyzer.variable(MARKER);
      }
      assert ! isParseTreeNode(b.element);

    } else {
      assert ! isParseTreeNode(tmp);

      tmp = new Binding(analyzer.variable(MARKER), tmp);
      tmp.setLocation(e); // Preserve the location.
    }

    // Void out the element.
    VoidedElement result = new VoidedElement(tmp);
    result.setLocation(e); // Preserve the location.

    // Done.
    return result;
  }

  /**
   * Bind and void the current regular, bindable element.
   *
   * @return The binding.
   */
  protected Binding bindAndVoid() {
    Sequence      s = sequences.get(sequenceIndex().index);
    VoidedElement v = bindAndVoid(s.get(elementIndex().index));
    s.elements.set(elementIndex().index, v);
    return (Binding)v.element;
  }

  /**
   * Process all elements in the current list of sequences.
   */
  protected void annotate() {
    // If any element explicitly sets the semantic value through an
    // action, then all hands are off.
    for (Sequence s : sequences) {
      for (Element e : s.elements) {
        if ((e instanceof Action) && ((Action)e).setsValue()) {
          // Increment toProcessIdx to make the decrement in
          // visit(Sequence) a no-op.
          toProcessIdx++;
          push();
          assert toProcessIdx == before.size();
          return;
        }
      }
    }

    // Next, if any element binds yyValue directly, we need to
    // preserve the explicit binding.
    int       valueSequenceIdx   = -1;
    int       valueElementIdx    = -1;
    boolean   requiresAnnotation = false;
    final int size               = sequences.size();
    for (int i=0; i<size; i++) {
      final Sequence s  = sequences.get(i);
      final int seqsize = s.hasTrailingChoice() ? s.size()-1 : s.size();
      for (int j=0; j<seqsize; j++) {
        // Skip any left-recursive nonterminal.
        if (isRecursive && (0 == i) && (0 == j)) continue;

        // Process the element.
        final Element e = s.get(j);

        if ((e instanceof Binding) &&
            CodeGenerator.VALUE.equals(((Binding)e).name)) {
          // Note that we track the last binding to yyValue,
          // overriding any previous bindings here.
          valueSequenceIdx = i;
          valueElementIdx  = j;
        } else if (isValuable(e)) {
          requiresAnnotation = true;
        }
      }
    }

    if (-1 != valueSequenceIdx) {
      if (! requiresAnnotation) {
        // Increment toProcessIdx to make the decrement in
        // visit(Sequence) a no-op.
        toProcessIdx++;
        push();
        assert toProcessIdx == before.size();
        return;

      } else if (requiresAnnotation) {
        Binding value = null;

        // Recreate the before and after bindings from scratch since
        // the previous list of sequences may not have contained a
        // binding to yyValue.
        before.clear();
        sequenceIdx.clear();
        elementIdx.clear();
        after.clear();

        for (int i=0; i<size; i++) {
          final Sequence s  = sequences.get(i);
          push();

          final int seqsize = s.hasTrailingChoice()? s.size()-1 : s.size();
          for (int j=0; j<seqsize; j++) {
            // Skip any left-recursive nonterminal.
            if (isRecursive && (0 == i) && (0 == j)) continue;

            // Process the element.
            Element e = s.get(j);

            if (i < toProcessIdx) {
              // The element has been processed.
              if ((i == valueSequenceIdx) && (j == valueElementIdx)) {
                // Record the (voided) binding to yyValue.
                value = (Binding)((VoidedElement)e).element;
              } else if (isBoundAndVoided(e)) {
                // Record a previously bound an voided element.
                if (null == value) {
                  before().add((Binding)((VoidedElement)e).element);
                } else {
                  after().add((Binding)((VoidedElement)e).element);
                }
              } else if (analyzer.isBindable(e) && (! isParseTreeNode(e))) {
                // Ensure the element has a binding.
                if (! (e instanceof Binding)) {
                  e = new Binding(analyzer.variable(MARKER), e);
                  s.elements.set(j, e);
                }
                if (null == value) {
                  before().add((Binding)e);
                } else {
                  after().add((Binding)e);
                }
              }

            } else if (isValuable(e)) {
              // The element has not yet been processed.
              VoidedElement v = bindAndVoid(e);
              s.elements.set(j, v);

              if ((i == valueSequenceIdx) && (j == valueElementIdx)) {
                value = (Binding)v.element;
              } else if (null == value) {
                before().add((Binding)v.element);
              } else {
                after().add((Binding)v.element);
              }
            }
          }
        }
        assert null != value; // We must have seen the binding.

        ParseTreeNode n = new ParseTreeNode(before(), value, after());
        Binding       b = new Binding(CodeGenerator.VALUE, n);
        sequences.get(sequences.size()-1).add(b);

        toProcessIdx    = sequences.size();
        assert toProcessIdx == before.size();
        return;
      }
    }

    // Now, process the elements, one at a time.
    for (int i=toProcessIdx; i<size; i++) {
      final Sequence s = sequences.get(i);
      push();

      for (int j=0; j < (s.hasTrailingChoice() ? s.size()-1 : s.size()); j++) {
        // Skip any left-recursive nonterminal.
        if (isRecursive && (0 == i) && (0 == j)) continue;

        // Process the element.
        final Element e = s.get(j);

        if (analyzer.isBindable(e)) {
          // The element represents a regular value.
          if ((isGeneric || isList) && AST.isList(analyzer.type(e))) {
            // If the current production is generic or list-valued and
            // the current element has a list value, we cannot include
            // the current element in an annotated node.
            if (hasValuable()) {
              // Emit a new annotated node.
              Binding b = hasBindable() ? bindAndVoid() : null;
              // Note: structural modification.
              s.elements.add(j, new ParseTreeNode(before(), b, after()));
              j++; // Do not revisit the current element.
            }
            reset();

          } else if ((! hasBindable()) || (! hasValuable())) {
            // If we have not yet seen any bindable or valuable
            // elements, we simply remember the current element
            // as the current bindable element.
            sequenceIndex().index = i;
            elementIndex().index  = j;

          } else {
            // Otherwise, we bind and void the current bindable
            // element and then add the corresponding parse tree node
            // to the current sequence.  Note that we shift the
            // current element to the right, which will then be
            // recorded as the current bindable element on the next
            // iteration.

            // Note: structural modification.
            s.elements.add(j, new ParseTreeNode(before(),bindAndVoid(),after()));
            reset();
          }

        } else if (isValuable(e)) {
          // The element is valuable.
          VoidedElement v = bindAndVoid(e);
          s.elements.set(j, v); // Update the sequence.

          if (! hasBindable()) {
            before().add((Binding)v.element);
          } else {
            after().add((Binding)v.element);
          }
        }
      }

      // Ensure that a parse tree node capturing a bindable element is
      // in the same sequence as the bindable element.  Otherwise, any
      // sequences with a higher index but visited later cannot see
      // the element.
      if (i < size-1) {
        if (hasBindable()) {
          if (hasValuable()) {
            // Note: structural modification.  Also note: we must
            // insert before the trailing choice.
            s.elements.add(s.size() - 1,
                           new ParseTreeNode(before(), bindAndVoid(), after()));
          }
          reset();
        }
      }
    }

    // Make sure we preserve any valuable elements.
    if (hasValuable()) {
      if (isGeneric && (! hasBindable())) {
        // The formatting node capturing the valuable elements needs
        // be created inside an action.
        sequences.get(sequences.size()-1).
          setProperty(Properties.FORMATTING, before());
      } else {
        Binding b = hasBindable() ? bindAndVoid() : null;
        // Note: structural modification.
        sequences.get(sequences.size()-1).
          add(new ParseTreeNode(before(), b, after()));
      }
    }

    // Remember that we have processed all sequences.
    toProcessIdx = sequences.size();
    assert toProcessIdx == before.size();
  }

  /**
   * Recursively process the specified element.
   *
   * @param e The element.
   */
  protected void recurse(Element e) {
    switch (e.tag()) {
    case BINDING:
    case OPTION:
    case REPETITION:
    case STRING_MATCH:
    case VOIDED:
      // Recurse on the unary operator's element.
      recurse(((UnaryOperator)e).element);
      break;

    case CHOICE:
    case SEQUENCE: {
      // Save the state.
      boolean             savedIsGeneric    = isGeneric;
      boolean             savedIsList       = isList;
      boolean             savedIsRecursive  = isRecursive;
      boolean             savedIsTopLevel   = isTopLevel;
      int                 savedToProcessIdx = toProcessIdx;
      List<Sequence>      savedSequences    = sequences;
      List<List<Binding>> savedBefore       = before;
      List<Index>         savedSequenceIdx  = sequenceIdx;
      List<Index>         savedElementIdx   = elementIdx;
      List<List<Binding>> savedAfter        = after;

      // Re-initialize the state.
      isGeneric    = false;
      isList       = false;
      isRecursive  = false;
      isTopLevel   = false;
      toProcessIdx = 0;
      sequences    = new ArrayList<Sequence>();
      before       = new ArrayList<List<Binding>>();
      sequenceIdx  = new ArrayList<Index>();
      elementIdx   = new ArrayList<Index>();
      after        = new ArrayList<List<Binding>>();
     
      // Actually recurse on the choice or sequence.
      dispatch(e);

      // Restore the state.
      isGeneric    = savedIsGeneric;
      isList       = savedIsList;
      isRecursive  = savedIsRecursive;
      isTopLevel   = savedIsTopLevel;
      toProcessIdx = savedToProcessIdx;
      sequences    = savedSequences;
      before       = savedBefore;
      sequenceIdx  = savedSequenceIdx;
      elementIdx   = savedElementIdx;
      after        = savedAfter;
    } break;

    default:
      // Nothing to do.
    }
  }

  /** Visit the specified grammar. */
  public void visit(Module m) {
    // Take care of generic productions first.
    new Detector().dispatch(m);
    new Rewriter().dispatch(m);

    // Initialize the per-grammar state.
    analyzer.register(this);
    analyzer.init(m);

    // Annotate the grammar's productions.
    for (Production p : m.productions) {
      // Do not process lexical productions or void productions that
      // do not consume any input.
      if (p.getBooleanProperty(Properties.LEXICAL) ||
          (AST.isVoid(p.type) &&
           (! p.getBooleanProperty(Properties.CONSUMER)))) {
        continue;
      }

      boolean processed = false;
      if (isSingleRepetition((FullProduction)p)) {
        for (Sequence s : p.choice.alternatives) {
          // Note that we can safely call recurse() since
          // analyzer.current() is only accessed for left-recursive
          // productions.
          recurse(s.get(0));
        }
        processed = true;

      } else if (AST.isVoid(p.type) ||
                 AST.isString(p.type) ||
                 AST.isNode(p.type) ||
                 AST.isAny(p.type)) {
        analyzer.process(p);
        processed = true;

      } else if (AST.isList(p.type)) {
        final Type elem = AST.getArgument(p.type);

        if (AST.isString(elem) || AST.isNode(elem) || AST.isAny(elem)) {
          analyzer.process(p);
          processed = true;
        }
      }

      if (! processed) {
        // We don't know how to process the production.
        if ((! m.hasAttribute(Constants.ATT_NO_WARNINGS)) &&
            (! p.hasAttribute(Constants.ATT_NO_WARNINGS))) {
          runtime.warning("unable to add parse tree annotations", p);
        }
      }
    }

    // Retype the grammar's productions.
    for (Production p : m.productions) {
      // Skip productions that are not token-level but are lexical or
      // are void and do not consume the input.
      if ((! p.getBooleanProperty(Properties.TOKEN)) &&
          (p.getBooleanProperty(Properties.LEXICAL) ||
           (AST.isVoid(p.type) &&
            (! p.getBooleanProperty(Properties.CONSUMER))))) {
        continue;
      }

      if (p.getBooleanProperty(Properties.TOKEN)) {
        // The production is token-level.  Make it actually return a
        // token.
        p.type = AST.TOKEN;

      } else if (AST.isVoid(p.type)) {
        // The void production is not lexical and consumes the input.
        // Make it generic.
        p.type = AST.GENERIC;

      } else if (AST.isString(p.type) || AST.isToken(p.type)) {
        // The production is not lexical and returns a string or
        // token.  Make it return a node.
        p.type = AST.NODE;

      } else if (AST.isList(p.type)) {
        Type elem = AST.getArgument(p.type);

        if (AST.isString(elem) || AST.isToken(elem)) {
          // Change a list of strings or tokens into a list of nodes.
          p.type = AST.listOf(AST.NODE);
        }

      }
    }

    // Et voila.
  }

  /** Visit the specified production. */
  public void visit(FullProduction p) {
    isGeneric   = isGeneric(p);
    isList      = AST.isList(p.type);
    isRecursive = DirectLeftRecurser.isTransformable(p);
    isTopLevel  = true;
    dispatch(p.choice);
  }

  /** Visit the specified choice. */
  public void visit(OrderedChoice c) {
    final boolean rec = isRecursive;
    final boolean top = isTopLevel;
    isTopLevel        = false;

    for (Sequence alt : c.alternatives) {
      // If the current choice is top-level, set the flag for whether
      // the current sequence is directly left-recursive.
      if (top) {
        if (rec) {
          isRecursive = DirectLeftRecurser.
            isRecursive(alt, (FullProduction)analyzer.current());
        } else {
          isRecursive = false;
        }
      }

      dispatch(alt);
    }
  }

  /** Visit the specified sequence. */
  public void visit(Sequence s) {
    // Add the sequence to the list of sequences.
    sequences.add(s);

    // Iterate over the elements of this sequence.  However, we cannot
    // use a Java iterator, since annotate() may add elements to
    // sequences and, in the presence of trailing choices, may thus
    // cause a concurrent modification exception.  We do not need to
    // update the sequence's size, since all elements are recursed on
    // during the iteration getting us to an invocation of annotate().
    final int size = s.elements.size();
    for (int i=0; i<size; i++) {
      Element e = s.get(i);

      if ((size - 1 == i) && (e instanceof OrderedChoice)) {
        // Continue with the trailing choice.
        dispatch(e);
      } else {
        // Recurse on the element.
        recurse(e);
      }
    }

    // Process annotations.
    if (! s.hasTrailingChoice()) {
      annotate();
    }

    // Remove the sequence again.
    sequences.remove(sequences.size() - 1);

    // Pop the processing state.
    toProcessIdx--;
    pop();
    assert toProcessIdx == before.size();
  }

  // ==========================================================================

  /**
   * Determine whether the specified production effectively is
   * generic.  This method returns <code>true</code> if the specified
   * production is, in fact, generic or it is a void production that
   * also is non-lexical and consumes the input.
   *
   * @see Generifier#isGeneric(FullProduction)
   *
   * @param p The production.
   * @return <code>true</code> if the specified production should be
   *   treated as generic.
   */
  public static boolean isGeneric(FullProduction p) {
    return (Generifier.isGeneric(p) ||
            (AST.isVoid(p.type) &&
             (! p.getBooleanProperty(Properties.LEXICAL)) &&
             p.getBooleanProperty(Properties.CONSUMER)));
  }

  /**
   * Determine whether the specified production can have a semantic
   * value.  Any production that is not void or that consumes the
   * input can have a semantic value.  This method assumes that
   * productions have been correctly annotated with the {@link
   * Properties#CONSUMER} property.
   *
   * @param p The production.
   * @return <code>true</code> if the specified production can have a
   *   semantic value.
   */
  public static boolean isValuable(FullProduction p) {
    return (! AST.isVoid(p.type)) ||
      p.getBooleanProperty(Properties.CONSUMER);
  }

  /**
   * Determine whether the specified type is a list type that can be
   * processed by this visitor.
   *
   * @param type The type.
   * @return <code>true</code> if the specified type is a list type
   *   that can be processed by this visitor.
   */
  public static boolean isList(Type type) {
    if (! AST.isList(type)) return false;

    Type elem = AST.getArgument(type);

    return (AST.isAny(elem) || AST.isNode(elem) || AST.isString(elem));
  }

  /**
   * Determine whether the specified production recognizes only a
   * single repetition.  This method returns <code>true</code> if the
   * specified production returns a list of objects, nodes, generic
   * nodes, tokens, or strings and each alternative consists of only a
   * single, optionally bound repetition.
   *
   * @param p The production.
   * @return <code>true</code> if the specified production recognizes
   *   only a single repetition.
   */
  public static boolean isSingleRepetition(FullProduction p) {
    if (! isList(p.type)) return false;

    for (Sequence s : p.choice.alternatives) {
      if (1 != s.size()) return false;

      final Element e = s.get(0);
      if ((! (e instanceof Repetition)) &&
          (! ((e instanceof Binding) &&
              (((Binding)e).element instanceof Repetition)))) {
        return false;
      }
    }

    return true;
  }

}
